#include <stdlib.h>
#include <string.h>
#include <limits.h> // USHRT_MAX

#include "config.h"
#include "macros.h"
#include "simulate.h"
#include "hash.h"
#include "stralloc.h"

typedef struct malloc_block_s {
	unsigned short size;
	unsigned short ref;
} malloc_block_t;

typedef struct block_s {
	struct block_s *next;	/* next block in the hash chain */
	/* these two must be last */
	unsigned short size;	/* length of the string */
	unsigned short refs;	/* reference count    */
} block_t;

#define NEXT(x) (x)->next
#define REFS(x) (x)->refs
#define SIZE(x) (x)->size
#define BLOCK(x) (((block_t *)(x)) - 1)	/* pointer arithmetic */
#define STRING(x) ((char *)(x + 1))

/* TODO: should be set somewhere else */
static int max_string_length = 120;

/* TODO: used by ugly macro */
/* used temporarily by SVALUE_STRLEN() */
int svalue_strlen_size;

/*
   this code is not the same as the original code.  I cleaned it up to
   use structs to: 1) make it easier to check the driver for memory leaks
   (using MallocDebug on a NeXT) and 2) because it looks cleaner this way.
   --Truilkan@TMI 92/04/19

   modified to make calls to strlen() unnecessary and to remove superfluous
   calls to findblock().  -- Truilkan@TMI, 1992/08/05
 */

/*
 * stralloc.c - string management.
 *
 * All strings are stored in an extensible hash table, with reference counts.
 * free_string decreases the reference count; if it gets to zero, the string
 * will be deallocated.  add_string increases the ref count if it finds a
 * matching string, or allocates it if it cant.  There is no way to allocate
 * a string of a particular size to fill later (hash wont work!), so you'll
 * have to copy things from a static (or malloced and later freed) buffer -
 * that is, if you want to avoid space leaks...
 *
 * Current overhead:
 *	sizeof(block_t) per string (string pointer, next pointer, and a short
 *  for refs). Strings are nearly all fairly short, so this is a significant
 *  overhead - there is also the 4 byte malloc overhead and the fact that
 *  malloc generally allocates blocks which are a power of 2 (should write my
 *	own best-fit malloc specialised to strings); then again, GNU malloc
 *	is bug free...
 */

/*
 * there is also generic hash table management code, but strings can be shared
 * (that was the point of this code), will be unique in the table,
 * require a reference count, and are malloced, copied and freed at
 * will by the string manager.  Besides, I wrote this code first :-).
 * Look at htable.c for the other code.  It uses the Hash() function
 * defined here, and requires hashed objects to have a pointer to the
 * next element in the chain (which you specify when you call the functions).
 */

#define StrHash(s) (whashstr((s), 20) & (htable_size_minus_one))

#define hfindblock(s, h) sfindblock(s, h = StrHash(s))
#define findblock(s) sfindblock(s, StrHash(s))

static block_t *sfindblock(char *, int);

/*
 * hash table - list of pointers to heads of string chains.
 * Each string in chain has a pointer to the next string and a
 * reference count (char *, int) stored just before the start of the string.
 * HTABLE_SIZE is in config.h, and should be a prime, probably between
 * 1000 and 5000.
 */

static block_t **base_table = (block_t **) 0;
static int htable_size;
static int htable_size_minus_one;

static block_t *alloc_new_string(char *, int);

void init_strings()
{
	int x, y;

	/* ensure that htable size is a power of 2 */
	y = HTABLE_SIZE;
	for (htable_size = 1; htable_size < y; htable_size *= 2)
		;
	htable_size_minus_one = htable_size - 1;
	base_table = CALLOCATE(htable_size, block_t *);

	for (x = 0; x < htable_size; x++) {
		base_table[x] = 0;
	}
}

/*
 * Looks for a string in the table.  If it finds it, returns a pointer to
 * the start of the string part, and moves the entry for the string to
 * the head of the pointer chain.  One thing (blech!) - puts the previous
 * pointer on the hash chain into fs_prev.
 */

static block_t * sfindblock(char *s, int h)
{
	block_t *curr, *prev;

	curr = base_table[h];
	prev = 0;

	while (curr) {
		if (*(STRING(curr)) == *s && !strcmp(STRING(curr), s)) {	/* found it */
			if (prev) {		/* not at head of list */
				NEXT(prev) = NEXT(curr);
				NEXT(curr) = base_table[h];
				base_table[h] = curr;
			}
			return (curr);	/* pointer to string */
		}
		prev = curr;
		curr = NEXT(curr);
	}
	return ((block_t *) 0);	/* not found */
}

char * findstring(char *s)
{
	block_t *b;

	if ((b = findblock(s))) {
		return STRING(b);
	} else {
		return 0;
	}
}

/* alloc_new_string: Make a space for a string.  */
static block_t * alloc_new_string(char *string, int h)
{
	block_t *b;
	int len = strlen(string);
	int size;

	if (len > max_string_length) {
		len = max_string_length;
	}
	size = sizeof(block_t) + len + 1;
	b = (block_t *)malloc(size);
	strncpy(STRING(b), string, len);
	STRING(b)[len] = '\0';	/* strncpy doesn't put on \0 if 'from' too
				 * long */
	SIZE(b) = (len > USHRT_MAX ? USHRT_MAX : len);
	REFS(b) = 1;
	NEXT(b) = base_table[h];
	base_table[h] = b;
	return (b);
}

char * make_shared_string(char *str)
{
	block_t *b;
	int h;

	b = hfindblock(str, h);	/* hfindblock macro sets h = StrHash(s) */
	if (!b) {
		b = alloc_new_string(str, h);
	} else {
		if (REFS(b))
			REFS(b)++;
	}
	return (STRING(b));
}

/*
ref_string: Fatal to call this function on a string that isn't shared.
 */
char * ref_string(char *str)
{
	block_t *b;

	b = BLOCK(str);
#ifdef DEBUG
	if (b != findblock(str)) {
		fatal("stralloc.c: called ref_string on non-shared string: %s.\n", str);
	}
#endif				/* defined(DEBUG) */
	if (REFS(b))
		REFS(b)++;
	return str;
}

/* free_string: fatal to call free_string on a non-shared string */
/*
 * free_string - reduce the ref count on a string.  Various sanity
 * checks applied.
 */
void free_string(char *str)
{
	block_t **prev, *b;
	int h;

	b = BLOCK(str);
	DEBUG_CHECK1(b != findblock(str),"stralloc.c: free_string called on non-shared string: %s.\n", str);

	/*
	 * if a string has been ref'd USHRT_MAX times then we assume that its used
	 * often enough to justify never freeing it.
	 */
	if (!REFS(b))
		return;

	REFS(b)--;

	if (REFS(b) > 0)
		return;

	h = StrHash(str);
	prev = base_table + h;
	while ((b = *prev)) {
		if (STRING(b) == str) {
			*prev = NEXT(b);
			break;
		}
		prev = &(NEXT(b));
	}

	DEBUG_CHECK1(!b, "free_string: not found in string table! (\"%s\")\n", str);

	free(b);
}

void deallocate_string(char *str)
{
	int h;
	block_t *b, **prev;

	h = StrHash(str);
	prev = base_table + h;
	while ((b = *prev)) {
		if (STRING(b) == str) {
			*prev = NEXT(b);
			break;
		}
		prev = &(NEXT(b));
	}
	DEBUG_CHECK1(!b,"stralloc.c: deallocate_string called on non-shared string: %s.\n", str);

	free(b);
}

/* This stuff needs a bit more work, otherwise FREE_MSTR() will crash on this
   malloc_block_t the_null_string_blocks[2] = { { 0, 1 }, { 0, 0 } };

   char *the_null_string = (char *)&the_null_string_blocks[1];
 */
char *int_new_string(int size)
{
	malloc_block_t *mbt;

	mbt = (malloc_block_t *)malloc(size + sizeof(malloc_block_t) + 1);
	if (size < USHRT_MAX) {
		mbt->size = size;
	} else {
		mbt->size = USHRT_MAX;
	}
	mbt->ref = 1;
	return (char *)(mbt + 1);
}

char *extend_string(char *str, int len) {
	malloc_block_t *mbt;

	mbt = (malloc_block_t *)realloc(MSTR_BLOCK(str), len + sizeof(malloc_block_t) + 1);
	if (len < USHRT_MAX) {
		mbt->size = len;
	} else {
		mbt->size = USHRT_MAX;
	}

	return (char *)(mbt + 1);
}

char *int_alloc_cstring(char *str)
{
	char *ret;

	ret = (char *)malloc(strlen(str) + 1);
	strcpy(ret, str);
	return ret;
}
